package _11_binary_search_tree;

/**
 * @author: mornd
 * @dateTime: 2023/6/12 - 17:39
 * 二叉搜索树 key 为 Comparable 的实现类
 */
public class BSTree2<K extends Comparable<K>, V> {
    BSTNode<K, V> root;

    /**
     * 查找关键字对应的值
     *
     * @param key
     * @return
     */
    public V get(K key) {
        BSTNode<K, V> curr = root;
        while (curr != null) {
            int c = curr.key.compareTo(key);
            if(c > 0) {
                curr = curr.left;
            } else if(c < 0) {
                curr = curr.right;
            } else {
                return curr.value;
            }
        }
        return null;
    }

    /**
     * 树节点
     */
    static class BSTNode<K extends Comparable<K>, V> {
        public K key;
        public V value;
        BSTNode<K, V> left;
        BSTNode<K, V> right;

        public BSTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}
